1858B - The Walkway - CodeForces Solution

//Partho Pratim Choudhury 2112003 (partho_03) 
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<climits>
#include<queue>
#include<stack>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
#include<cstring>
#include<bitset>
#include<bits/stdc++.h>

#define int         long long
#define ll          long long
#define fr(i,k,n)   for(ll i=k;i<n;i++)
#define rfr(i,n,k)  for(ll i=n;i>=k;i--)
#define inp(vec,n)    fr(i,0,n){cin >> vec[i];} 
#define all(x)      (x).begin(),(x).end()
#define vll         vector<ll>
#define vpll        vector<pair<ll, ll>> 
#define mll         map<ll,ll> 
#define p_b         push_back
#define br          '\n'
#define print(a,n)  for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl;
#define fbo(k)      find_by_order(k) // returns an iterator to kth element in ordered set (zero based index)
#define ook(k)      order_of_key(k) // counts the elements which are strictly less than key k in ordered set
#define max_pq      priority_queue<ll> 
#define min_pq      priority_queue<ll, vll, greater<ll>>

using namespace std;
// using namespace __gnu_pbds;

// template<typename T>
// using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //required to perform set operations with indexing facility

// void google(i){
//     cout << "Case #" << i << ": ";
// }

/**************************************Number theory starts********************************************/
const int M=1e9+7;
//1. Binary exponentiation (log p)
ll power(ll b, ll p){ll res=1; while(p!=0){ if(p&1){ res=res*b; p--;} else{ b=b*b; p=p/2;}} return res;}

//2. Fermats little theorem (log m) provided m is prime and b and m are relatively prime
ll modPow(ll b, ll p, ll m){ll res=1; while(p!=0){ if(p&1){ res=(res*b)%m; p--;} else{ b=(b*b)%m; p=p/2;}} return res;}
ll phi(ll n){ ll res=n; for(ll i=2;i*i<=n;i++){ if(n%i==0){ res=res/i; res=res*(i-1);} while(n%i==0){ n=n/i;}} if(n>1){ res=res/n; res=res*(n-1); } return res;}

ll mod(ll x){  return ((x%M + M)%M);}
ll add(ll a, ll b){  return mod(mod(a)+mod(b));}
ll mul(ll a, ll b){  return mod(mod(a)*mod(b));}
ll inv(ll x){  return modPow(x,M-2,M);}
ll divide(ll a, ll b){ return mul(a,inv(b));}
ll lcm(ll a, ll b){return (a / __gcd(a, b)) * b;}
// ll nCr(ll n, ll r){  return divide(fact[n],mul(fact[r],fact[n-r]));}

/****************************************Number theory ends**********************************************/

/***********************************Disjoint Set Union Starts********************************************/
// class DisjointSet{
//     vector<int> rank, parent, size;
//     public: 
//     DisjointSet(int n){
//         rank.resize(n+1, 0);
//         parent.resize(n+1);
//         size.resize(n+1,1);
//         for(int i = 0; i <= n; i++){
//             parent[i] = i;
//         }
//     }  

//     int findUPar(int node){
//         if(node == parent[node]){
//             return node;
//         }
//         return parent[node] = findUPar(parent[node]);
//     }

//     void unionByRank(int u, int vec){
//         int ul_pu = findUPar(u);
//         int ul_pv = findUPar(vec);
//         if(ul_pu == ul_pv) return;
//         if(rank[ul_pu] < rank[ul_pv]){
//             parent[ul_pu] = ul_pv;
//         }
//         else if(rank[ul_pv] < rank[ul_pu]){
//             parent[ul_pv] = ul_pu;
//         }else{
//             parent[ul_pv] = ul_pu;
//             rank[ul_pu]++; 
//         }
//     }

//     void unionBySize(int u, int vec){
//         int ul_pu = findUPar(u);
//         int ul_pv = findUPar(vec);
//         if(ul_pu == ul_pv) return;
//         if(size[ul_pu] < size[ul_pv]){
//             parent[ul_pu] = ul_pv;
//             size[ul_pv] += size[ul_pu];
//         }else{
//             parent[ul_pv] = ul_pu;
//             size[ul_pu] += size[ul_pv]; 
//         }
//     }
// };
/************************************Disjoint Set Union Ends*********************************************/


void solve(){
    // cout << "hello" << endl;
    int n, m, d;
    cin >> n >> m >> d;
    vll vec(m);
    fr(i,0,m){
        cin >> vec[i];
    }
    vll prefix(m, 0);
    vll suffix(m, 0);
    rfr(i, m-1, 0){
        if (i == m-1){
            if (vec[i] == n){
                suffix[i] = 1;
            }else{
                suffix[i] = 1 + (n - vec[i]) / d;
            }
        }else{
            suffix[i] = suffix[i+1] + (vec[i+1] - vec[i]) / d;
            if ((vec[i + 1] - vec[i]) % d){
                suffix[i]++;
            }
        }
    }
    fr(i, 0, m){
        if (i == 0){
            if (vec[i] == 1){
                prefix[i] = 1;
            }else{
                prefix[i] = 1 + (vec[i] - 1) / d;
                if ((vec[i] - 1) % d){
                    prefix[i]++;
                }
            }
        }else{
            prefix[i] = prefix[i-1] + (vec[i] - vec[i-1]) / d;
            if ((vec[i] - vec[i-1]) % d){
                prefix[i]++;
            }
        }
    }
    map<int, int> mp;
    for (int i = 0; i < m; i++){
        int ans;
        if (i == 0){
            ans = 1 + suffix[i+1] + ((vec[i+1] - 1) / d);
            if ((vec[i+1] - 1) % d == 0){
                ans--;
            }
            mp[ans]++;
        }
        else if (i == m - 1){
            ans = prefix[i-1] + ((n - vec[i-1]) / d);
            mp[ans]++;
        }else{
            ans = prefix[i-1] + suffix[i+1] + ((vec[i+1] - vec[i-1]) / d);
            if ((vec[i+1] - vec[i-1]) % d == 0){
                ans--;
            }
            mp[ans]++;
        }
    }
    cout << mp.begin()->first << " " << mp.begin()->second << endl;
    return;
}

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    #ifndef ONLINE_JUDGE
        freopen("input.txt","r+",stdin);
        freopen("output.txt","w+",stdout);
    #endif
    ll t=1;
    cin>>t;
    for(ll i=1;i<=t;i++){
        // google(i);
        solve();
    }

    return 0;
}